package com.rayboo.example.algorithm.sort;

import com.rayboo.example.util.ArrayUtils;

import java.util.Arrays;

/**
 * 堆排序
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>堆排序是一种树形选择排序算法，其原理是将R[1…n]看成一棵完全二叉树的顺序存储结构。
 * 利用完全二叉树中双亲节点和孩子结点的关系，在当前无序区中选择关键字最大（最小）的元素构建成大根堆（小根堆）。
 * 堆排序的主要流程便是，建立大（小）根堆，然后输出元素（顶部和底部元素进行交换），再调整堆，直到元素全部输出。
 * 堆排序是一个不稳定的算法。
 *
 * <p>https://www.runoob.com/w3cnote/heap-sort.html
 * <p>https://www.jianshu.com/p/73ef54fb99f4
 */
public class HeapSort {

    public static void main(String[] args) {
        int arr[] = ArrayUtils.randomNoRepeatIntArray(0, 100, 10);
        System.out.println("排序前：\n" + Arrays.toString(arr));

        heapSort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));
    }

    /**
     * 堆排序
     *
     * @param arr 数组
     * @return 排序后的数组
     */
    private static int[] heapSort(int[] arr) {
        int i, j, temp;

        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         *
         * 建立堆，从最后一个非叶子节点开始
         */
        for (i = (arr.length - 2) / 2; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         *
         * 完成排序，从最后一个元素进行输出，每次循环确定一个元素的位置
         */
        for (j = arr.length - 1; j >= 1; j--) {
//            temp = arr[0];
//            arr[0] = arr[j];
//            arr[j] = temp;

            // 交换数据
            swap(arr, 0, j);

            // 筛选 R[0] 结点，得到i个结点的堆
            adjustHeap(arr, 0, j);
        }

        return arr;
    }

    /**
     * 数据交换
     *
     * @param array 数组
     * @param i 源索引
     * @param j 目标索引
     */
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 调整堆
     *
     * @param arr 数组
     * @param low 需要堆化处理的数据的索引
     * @param length 未排序的堆（数组）的长度
     */
    private static void adjustHeap(int[] arr, int low, int length) {
        //设置堆顶的值
        int temp = arr[low];
        //从左边的堆开始判断
        for (int i = low * 2 + 1; i <= length - 1; i = 2 * i + 1) {
            //如果左边的堆小于右边的堆
            if (i + 1 < length && arr[i] < arr[i + 1]) {
                //取右边的堆
                i++;
            }

            //如果堆顶的值大于左右堆中的较大者，无需调整
            if (temp >= arr[i]) {
                break;
            } else {
                //否则的话，将左右堆中的较大者换到双亲节点
                arr[low] = arr[i];
                //然后将low值更新，方便继续向下调整
                low = i;
            }
        }

        //将原堆顶位置当入最后调整出来的地方
        arr[low] = temp;
    }
}
